package com.sheng.leetcode.year2023.month08.day15;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author by ls
 * @date 2023/8/15
 * <p>
 * 833. 字符串中的查找与替换<p>
 * <p>
 * 你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。<p>
 * 替换操作以三个长度均为 k 的并行数组给出：indices, sources,  targets。<p>
 * 要完成第 i 个替换操作:<p>
 * 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。<p>
 * 如果没有出现， 什么也不做 。<p>
 * 如果出现，则用 targets[i] 替换 该子字符串。<p>
 * 例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。<p>
 * 所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。<p>
 * 例如，一个 s = "abc" ，  indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，<p>
 * 因为 "ab" 和 "bc" 替换重叠。<p>
 * 在对 s 执行所有替换操作后返回 结果字符串 。<p>
 * 子字符串 是字符串中连续的字符序列。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]<p>
 * 输出："eeebffff"<p>
 * 解释：<p>
 * "a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。<p>
 * "cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]<p>
 * 输出："eeecd"<p>
 * 解释：<p>
 * "ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。<p>
 * "ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length <= 1000<p>
 * k == indices.length == sources.length == targets.length<p>
 * 1 <= k <= 100<p>
 * 0 <= indexes[i] < s.length<p>
 * 1 <= sources[i].length, targets[i].length <= 50<p>
 * s 仅由小写英文字母组成<p>
 * sources[i] 和 targets[i] 仅由小写英文字母组成<p>
 */
public class LeetCode0833 {

    @Test
    public void test01() {
        String s = "abcd";
        int[] indices = {0, 2};
//        String[] sources = {"a", "cd"}, targets = {"eee", "ffff"};
        String[] sources = {"ab", "ec"}, targets = {"eee", "ffff"};
        System.out.println(new Solution().findReplaceString(s, indices, sources, targets));
    }
}

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = indices.length;
        // 数组 indices 未排序，需要优先进行排序
        int[][] temp = new int[indices.length][2];
        for (int i = 0; i < n; i++) {
            temp[i][0] = indices[i];
            temp[i][1] = i;
        }
        Arrays.sort(temp, Comparator.comparingInt(o -> o[0]));
        // 上一次计算的字符串 s 的起始位置
        int index = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            // 要从字符串 s 中选取的起始位置
            int in = temp[i][0];
            // 该位置的目标字符串
            String source = sources[temp[i][1]];
            // 目标字符串的长度
            int length = source.length();
            // 目标字符串的长度不得大于字符串 s 剩余的长度
            if (in + length <= s.length()) {
                // 获取
                String substring = s.substring(in, in + length);
                // 判断是否和目标字符串相等
                if (substring.equals(source)) {
                    sb.append(s, index, in).append(targets[temp[i][1]]);
                    index = in + length;
                }
            }
        }
        // 判断是否存在未添加的剩余字符串
        if (index != s.length()) {
            sb.append(s.substring(index));
        }
        return sb.toString();
    }
}
